Date: Mon, 25 Nov 1996 22:03:31 GMT
Server: NCSA/1.4.1
Content-type: text/html
Last-modified: Wed, 09 Aug 1995 00:13:41 GMT
Content-length: 4947

<html><head><title>Alan Siegel</title>
<link rev="made" href="mailto:siegel@cs.nyu.edu (Alan Siegel)">
</head>
<body>

<H1>Alan Siegel</H1>
<H2>Associate Professor, Computer Science Dept</H2>
<H2> <!WA0><A HREF="http://found.cs.nyu.edu/cgi-bin/finger?siegel@merv">Alan Siegel@cs.nyu.edu</H2>

<HR>

<!WA1><a HREF="http://cs.nyu.edu/">
Department of Computer Science<br>
</a>
<!WA2><a HREF="http://cs.nyu.edu/cs/courantnyu.html">
Courant Institute of Mathematical Sciences<br>
</a>
<!WA3><a HREF="http://nyu.edu/">New York University<p>
</a>

<HR>

<PRE><H2>Mail Address</H2>
      <!WA4><a HREF="http://cs.nyu.edu/cs/faculty/siegel/wsq-campus.html">Courant Inst. of Math. Sciences</a>, rm 413<br>
      251 Mercer St.<br>
      New York, NY 10012, U.S.A.<p>
</PRE>

<PRE><H2>Phones</H2>
      212.998.3122 (voice)   212.995.4121 (fax)<p>
</PRE>

<PRE><H2>Email</H2><I>
      <!WA5><A HREF="http://found.cs.nyu.edu/cgi-bin/finger?siegel@merv">Alan Siegel@cs.nyu.edu</A>
</I></PRE>

<HR>

<H2>Topics</H2>

<ul>
<li>SODA 95 paper<!WA6><a href="http://cs.nyu.edu/cs/faculty/siegel/soda.ps">PostScript</A>
</ul>
</ul>


<P>
<dt><!WA7><a href="file://cs.nyu.edu/pub/tech-reports/tr684.ps.gz">tr684 </a>
<dd> A. Siegel,
"On Universal Classes of Extremely Random Constant Time Hash Functions
and their Time-space Tradeoff",
Apr. 1995

<P>
Abstract: 
A family of functions F that map [0,n]->[0,n], is said to be h-wise independent
if any h points in [0,n] have an image, for randomly selected f in F, that is
uniformly distributed.  This paper gives both probabilistic and explicit
randomized constructions of (n**epsilon)-wise independent functions, for
epsilon<1, that can be evaluated in constant time for the standard random
access model of computation.  Simple extensions give comparable behavior for
larger domains.  As a consequence, many probabilistic algorithms can for the
first time be shown to achieve their expected asymptotic performance for a
feasible model of computation.
<P>
This paper also establishes a tight tradeoff in the number of random seeds that
must be precomputed for a random function that runs in time T and is h-wise
independent.
<dd></dt>
 
<P>
<dt><!WA8><a href="file://cs.nyu.edu/pub/tech-reports/tr685.ps.gz">tr685 </a>
<dd> A. Siegel,
"Toward a Usable Theory of Chernoff Bounds for Heterogeneous and Partially
Dependent Random Variables",
Apr. 1995

<P>
Abstract:
Let X be a sum of real valued random variables and have a bounded mean E[X].
The generic Chernoff-Hoeffding estimate for large deviations of X is:
P{X-E[X]>=a}<=min_{y>=0}exp(-y(a+E[X]))E[exp(y X)], which applies with a>=0
to random variables with very small tails.  At issue is how to use this method
to attain sharp and useful estimates. We present a number of Chernoff-Hoeffding
bounds for sums of random variables that may have a variety of dependent
relationships and that may be heterogeneously distributed.
<dd></dt>

<P>
<dt><!WA9><a href="file://cs.nyu.edu/pub/tech-reports/tr686.ps.gz">tr686 </a>
<dd> J. Schmidt, A. Siegel,
"Double Hashing is Computable and Randomizable with Universal Hash Functions",
Apr. 1995

<P>
Abstract:
Universal hash functions that exhibit (c log n)-wise independence are shown to
give a performance in double hashing and virtually any reasonable
generalization of double hashing that has an expected probe count of
1/(1-alpha) + epsilon for the insertion of the (alpha n)-th item into a table
of size n, for any fixed alpha < 1 and epsilon > 0.  This performance is within
epsilon of optimal.  These results are derived from a novel formulation that
overestimates the expected probe count by underestimating the presence of
partial items already inserted into the hash table, and from a sharp analysis
of the underlying stochastic structures formed by colliding items.
<dd></dt>
 
<P>
<dt><!WA10><a href="file://cs.nyu.edu/pub/tech-reports/tr687.ps.gz">tr687 </a>
<dd> A. Siegel, J. Schmidt,
"Closed Hashing is Computable and Optimally Randomizable with Universal
 Hash Functions",
Apr. 1995

<P>
Abstract:
Universal hash functions that exhibit (c log n)-wise independence are shown to
give a performance in double hashing, uniform hashing and virtually anyreasonable generalization of double hashing that has an expected probe count of
1/(1-alpha)+O(1/n) for the insertion of the (alpha n)-th item into a table of
size n, for any fixed alpha < 1.  This performance is optimal.  These results
are derived from a novel formulation that overestimates the expected probe
count by underestimating the presence of local items already inserted into the
hash table, and from a very sharp analysis of the underlying stochasticstructures formed by colliding items.
<P>
Analogous bounds are attained for the expected r-th moment of the probe count,
for any fixed r, and linear probing is also shown to achieve a performance
with universal hash functions that is equivalent to the fully random case.
<dd></dt>

<P>
<li>NYU Tech Reports<!WA11><a href="file://cs.nyu.edu/pub/tech-reports/tr.html">hypertext</A>

<HR>
<HR>

</body>
</html>

